package com.c2b.algorithm.leetcode.lcr;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href='https://leetcode.cn/problems/add-two-numbers-ii/'> 两数相加 II(Add Two Numbers II)</a>
 * <p>给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。</p>
 * <p>你可以假设除了数字 0 之外，这两个数字都不会以零开头。</p>
 *
 * <p>
 * <pre>
 * 示例1：
 *      输入：l1 = [7,2,4,3], l2 = [5,6,4]
 *      输出：[7,8,0,7]
 *
 * 示例2：
 *      输入：l1 = [2,4,3], l2 = [5,6,4]
 *      输出：[8,0,7]
 *
 * 示例3：
 *      输入：l1 = [0], l2 = [0]
 *      输出：[0]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>链表的长度范围为 [1, 100]</li>
 *     <li>0 <= node.val <= 9</li>
 *     <li>输入数据保证链表代表的数字无前导 0</li>
 * </ul>
 * </p>
 * <b>进阶：如果输入链表不能翻转该如何解决？</b>
 *
 * @author c2b
 * @since 2024/3/19 17:29
 */
public class LCR025 {
    static class Solution {

        /**
         * 不使用链表 - 栈
         */
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            if (l1 == null) {
                return l2;
            }
            if (l2 == null) {
                return l1;
            }
            Deque<Integer> stack1 = new LinkedList<>();
            while (l1 != null) {
                stack1.addLast(l1.val);
                l1 = l1.next;
            }
            Deque<Integer> stack2 = new LinkedList<>();
            while (l2 != null) {
                stack2.addLast(l2.val);
                l2 = l2.next;
            }
            int carry = 0;
            ListNode resultNode = null;
            while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
                int sum = carry;
                if (!stack1.isEmpty()) {
                    sum += stack1.removeLast();
                }
                if (!stack2.isEmpty()) {
                    sum += stack2.removeLast();
                }
                carry = sum / 10;
                resultNode = new ListNode(sum % 10, resultNode);
            }
            return resultNode;
        }

        /**
         * 反转链表
         */
        public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
            if (l1 == null) {
                return l2;
            }
            if (l2 == null) {
                return l1;
            }
            l1 = reserve(l1);
            l2 = reserve(l2);
            ListNode dummyHead = new ListNode(-1);
            ListNode currNode = dummyHead;
            int carry = 0;
            while (l1 != null || l2 != null || carry != 0) {
                int sum = carry;
                if (l1 != null) {
                    sum += l1.val;
                    l1 = l1.next;
                }
                if (l2 != null) {
                    sum += l2.val;
                    l2 = l2.next;
                }
                carry = sum / 10;
                currNode.next = new ListNode(sum % 10);
                currNode = currNode.next;
            }
            return reserve(dummyHead.next);
        }

        private ListNode reserve(ListNode head) {
            ListNode prevNode = null;
            ListNode currNode = head;
            ListNode nextNode;
            while (currNode != null) {
                nextNode = currNode.next;
                currNode.next = prevNode;
                prevNode = currNode;
                currNode = nextNode;
            }
            return prevNode;
        }
    }
}
